package com.srunpass.algorithm;

import java.util.Arrays;

public class 买卖股票的最佳时机IV {

    public static void main(String[] args) {
        买卖股票的最佳时机IV 买卖股票的最佳时机IV = new 买卖股票的最佳时机IV();
        int k =2;
        int [] prices = {1};
        买卖股票的最佳时机IV.maxProfit(k,prices);
    }



    public int maxProfit(int k, int[] prices) {
        //第n次买入最大收益
        int[] buy = new int[k];
        //第n次卖出最大收益
        int[] sell = new int[k];
        Arrays.fill(buy, -prices[0]);
        for (int price : prices) {
            for (int j = 0; j < k; j++) {
                if (j == 0) {
                    buy[j] = Math.max(buy[j], -price);
                } else {
                    buy[j] = Math.max(buy[j], sell[j - 1] - price);
                }
                sell[j] = Math.max(sell[j], price + buy[j]);
            }
        }
        return sell[k - 1];
    }
}
